The present invention relates to a method and apparatus for performing finite field and integer arithmetic.
Elliptic Curve (EC) cryptography over a finite field requires the arithmetic operations of addition, multiplication, squaring and inversion. Additionally, subtraction operations are also required if the field is not of characteristic two. Modular arithmetic operations are also required, for example in computing signatures, however these operations are required less frequently than the finite field operations. EC cryptography as an example, requires the full complement of modular and finite field operations, addition, subtraction, multiplication and inversion.
Field sizes for cryptography tend to be relatively large, requiring fast, dedicated processors to perform the arithmetic operations in an acceptable time. Thus there have been numerous implementations of either fast modular arithmetic processors or dedicated processors for performing arithmetic operations in F2n. The use of special purpose or dedicated processors is well known in the art. These processors are generally termed coprocessors and are normally utilized in a host computing system, whereby instructions and control is provided to the compressor from a main processor.
Traditionally RSA was the encryption system of choice, however with the advent of superior and more secure EC cryptography the need for processors that perform modular exponentiation exclusively is becoming less imperative. However, while users are in transition from RSA cryptography to EC cryptography there is a need for an arithmetic processor that supports both these operations, with little or no penalty in performance and cost.
It is an object of the present invention to obviate or mitigate some of the above disadvantages.
In accordance one aspect of the present invention there is provided an arithmetic processor comprising:
a) an arithmetic logic unit to perform field operations in an underlying finite field;
b) at least one register to contain a representation of an operand; and
c) a control unit to control operations of said arithmetic logic unit on said operand.
The register has at least one control bit in a predetermined location in the register and co-operates with the arithmetic logic unit to compensate for variations in the size of the underlying finite field.
In accordance with a further aspect of the present invention there is provided an arithmetic processor for performing cryptographic operations comprising a first arithmetic logic unit for performing finite fields operations, a second arithmetic logic unit for performing a different cryptographic operation and a set of registers to hold representations of operands to be operated upon by the arithmetic logic unit during the cryptographic operations. The set of registers is operably connected to each of the arithmetic logic units for making the contents of the registers available to one of the arithmetic logic units.
In accordance with a yet further aspect of the present invention, there is provided an arithmetic processor for performing finite field operations and including an arithmetic logic unit having a finite field arithmetic circuit comprising a finite field multiplier circuit having a plurality of registers for receiving representations of first and second operands and a further register for receiving a representation of a modulus and an accumulator for containing a finite field product of the operands, logic circuitry for establishing connections from respective cells of the registers to the accumulator and a sequencing controller operatively associated with the registers and the logic circuit for implementing a sequence of steps to derive the finite field product.
In accordance with a still further aspect of the present invention, there is provided an arithmetic processor comprising:
a) an arithmetic logic unit having a plurality of arithmetic circuits each for performing a group of associated arithmetic operations, the arithmetic logic unit having an operand input data bus for receiving operand data thereon and a result data output bus for returning the results of the arithmetic operations thereon;
b) a register file coupled to the operand data bus and the result data bus; and
c) a controller coupled to the arithmetic logic unit and the register file, the controller selecting one of the plurality of arithmetic circuits in response to a mode control signal requesting an arithmetic operation and for controlling data access between the register file and the arithmetic logic unit and whereby the register file is shared by the arithmetic circuits.
In accordance with another aspect of the present invention, there is provided an arithmetic processor for performing cryptographic operations comprising:
a) an arithmetic logic unit to perform field operations in an underlying finite field, the arithmetic logic unit having a special purpose register to contain an operand and an accumulating register, the accumulating register being coupled to the special purpose register to receive the operand therefrom;
b) a register file coupled to the special purpose register to provide the operand thereto, and thereby provide the operand to the accumulating register; and
c) a control unit to control operations of the arithmetic logic unit on the accumulating register;
the special purpose register cooperating with the arithmetic logic unit to compensate for variations in the size of the underlying finite field.
In accordance with yet another aspect of the present invention, there is provided an arithmetic processor for performing cryptographic operations comprising:
a) an arithmetic logic unit perform field operations in an underlying finite field;
b) a register file coupled to the arithmetic logic unit to provide an operand thereto;
c) a first control signal indicative of the size of the finite field;
d) a second control signal indicative of an operation; and
e) a controller to provide the control signals to the arithmetic logic unit and thereby perform the operation and compensate for variations in the size of the finite field.